package datastruct;

import java.util.LinkedList;

public class GetUglyNumber {

    /**
     * JZ33 丑数
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(GetUglyNumber_Solution(1500));
    }

    public static int GetUglyNumber_Solution(int index) {
        if (index <= 0){
            return 0;
        }
        int res = 1;
        index--;

        LinkedList<Integer> queue2 = new LinkedList<>();
        LinkedList<Integer> queue3 = new LinkedList<>();
        LinkedList<Integer> queue5 = new LinkedList<>();

        queue2.addLast(res * 2);
        queue3.addLast(res * 3);
        queue5.addLast(res * 5);

        while (index > 0){
            if (queue2.getFirst() < queue3.getFirst()){
                if (queue2.getFirst() < queue5.getFirst()){
                    if (res == queue2.getFirst()){
                        queue2.pollFirst();
                        continue;
                    } else {
                        res = queue2.pollFirst();
                        index--;
                    }
                } else {
                    if (res != queue5.getFirst()){
                        res = queue5.pollFirst();
                        index--;
                    } else {
                        queue5.pollFirst();
                        continue;
                    }

                }
            } else {
                if (queue3.getFirst() < queue5.getFirst()){
                    if (queue3.getFirst() != res){
                        res = queue3.pollFirst();
                        index--;
                    } else {
                        queue3.pollFirst();
                        continue;
                    }
                } else {
                    if (queue5.getFirst() != res){
                        res = queue5.pollFirst();
                        index--;
                    } else {
                        queue5.pollFirst();
                        continue;
                    }

                }
            }
            queue2.addLast(res * 2);
            queue3.addLast(res * 3);
            queue5.addLast(res * 5);
        }
        return res;
    }
}
